home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / zoo21src.zoo / huf.c < prev    next >
C/C++ Source or Header  |  1991-07-24  |  8KB  |  357 lines
  1. /*$Source: g:/newzoo\RCS\huf.c,v $*/
  2. /*$Id: huf.c,v 1.4 1991/07/24 23:47:04 bjsjr Rel $*/
  3. /***********************************************************
  4.     huf.c -- static Huffman
  5.  
  6. Adapted from "ar" archiver written by Haruhiko Okumura.
  7. ***********************************************************/
  8. #include "options.h"
  9. #include "zoo.h"
  10. #include "ar.h"
  11. #include "lzh.h"
  12. #include "errors.i"
  13.  
  14. extern void prterror PARMS((int, char *, ...));
  15.  
  16. #ifdef ANSI_HDRS
  17. # include <stdlib.h>
  18. #endif
  19.  
  20. #define NP (DICBIT + 1)
  21. #define NT (CODE_BIT + 3)
  22. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  23. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  24. #if NT > NP
  25. # define NPT NT
  26. #else
  27. # define NPT NP
  28. #endif
  29.  
  30. int decoded;        /* for use in decode.c */
  31.  
  32. ushort left[2 * NC - 1], right[2 * NC - 1];
  33. static uchar *buf, c_len[NC], pt_len[NPT];
  34. static uint   bufsiz = 0, blocksize;
  35. static ushort c_freq[2 * NC - 1], c_table[4096], c_code[NC],
  36.               p_freq[2 * NP - 1], pt_table[256], pt_code[NPT],
  37.               t_freq[2 * NT - 1];
  38.  
  39. /***** encoding *****/
  40.  
  41. static void count_t_freq()
  42. {
  43.     int i, k, n, count;
  44.  
  45.     for (i = 0; i < NT; i++) t_freq[i] = 0;
  46.     n = NC;
  47.     while (n > 0 && c_len[n - 1] == 0) n--;
  48.     i = 0;
  49.     while (i < n) {
  50.         k = c_len[i++];
  51.         if (k == 0) {
  52.             count = 1;
  53.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  54.             if (count <= 2) t_freq[0] += count;
  55.             else if (count <= 18) t_freq[1]++;
  56.             else if (count == 19) {  t_freq[0]++;  t_freq[1]++;  }
  57.             else t_freq[2]++;
  58.         } else t_freq[k + 2]++;
  59.     }
  60. }
  61.  
  62. static void write_pt_len(n, nbit, i_special)
  63. int n;
  64. int nbit;
  65. int i_special;
  66. {
  67.     int i, k;
  68.  
  69.     while (n > 0 && pt_len[n - 1] == 0) n--;
  70.     putbits(nbit, (uint) n);
  71.     i = 0;
  72.     while (i < n) {
  73.         k = pt_len[i++];
  74.         if (k <= 6) putbits(3, (uint) k);
  75.         else putbits(k - 3, (uint) (((unsigned) 1 << (k - 3)) - 2));
  76.         if (i == i_special) {
  77.             while (i < 6 && pt_len[i] == 0) i++;
  78.             putbits(2, (uint) ((i - 3) & 3));
  79.         }
  80.     }
  81. }
  82.  
  83. static void write_c_len()
  84. {
  85.     int i, k, n, count;
  86.  
  87.     n = NC;
  88.     while (n > 0 && c_len[n - 1] == 0) n--;
  89.     putbits(CBIT, (uint) n);
  90.     i = 0;
  91.     while (i < n) {
  92.         k = c_len[i++];
  93.         if (k == 0) {
  94.             count = 1;
  95.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  96.             if (count <= 2) {
  97.                 for (k = 0; k < count; k++)
  98.                     putbits((int) pt_len[0], (uint) pt_code[0]);
  99.             } else if (count <= 18) {
  100.                 putbits((int) pt_len[1], (uint) pt_code[1]);
  101.                 putbits(4, (uint) (count - 3));
  102.             } else if (count == 19) {
  103.                 putbits((int) pt_len[0], (uint) pt_code[0]);
  104.                 putbits((int) pt_len[1], (uint) pt_code[1]);
  105.                 putbits(4, 15);
  106.             } else {
  107.                 putbits((int) pt_len[2], (uint) pt_code[2]);
  108.                 putbits(CBIT, (uint) (count - 20));
  109.             }
  110.         } else putbits((int) pt_len[k + 2], (uint) pt_code[k + 2]);
  111.     }
  112. }
  113.  
  114. #ifdef __GNUC__
  115. inline
  116. #endif
  117. static void encode_c(c)
  118. int c;
  119. {
  120.     putbits((int) c_len[c], (uint) c_code[c]);
  121. }
  122.  
  123. #ifdef __GNUC__
  124. inline
  125. #endif
  126. static void encode_p(p)
  127. uint p;
  128. {
  129.     uint c, q;
  130.  
  131.     c = 0;  q = p;  while (q) {  q >>= 1;  c++;  }
  132.     putbits((int) pt_len[c], (uint) pt_code[c]);
  133.     if (c > 1) putbits((int) (c - 1), (uint) (p & ((unsigned) 0xFFFF >> (17 - c))));
  134. }
  135.  
  136. static void send_block()
  137. {
  138.     uint i, k, flags, root, pos, size;
  139.  
  140.     root = make_tree(NC, c_freq, c_len, c_code);
  141.     size = c_freq[root];
  142. #if 0
  143.     /*debug*/ (void) fprintf(stderr, "\nsize = %u\n", size);
  144. #endif
  145.     putbits(16, size);
  146.     if (root >= NC) {
  147.         count_t_freq();
  148.         root = make_tree(NT, t_freq, pt_len, pt_code);
  149.         if (root >= NT) {
  150.             write_pt_len(NT, TBIT, 3);
  151.         } else {
  152.             putbits(TBIT, 0);  putbits(TBIT, root);
  153.         }
  154.         write_c_len();
  155.     } else {
  156.         putbits(TBIT, 0);  putbits(TBIT, 0);
  157.         putbits(CBIT, 0);  putbits(CBIT, root);
  158.     }
  159.     root = make_tree(NP, p_freq, pt_len, pt_code);
  160.     if (root >= NP) {
  161.         write_pt_len(NP, PBIT, -1);
  162.     } else {
  163.         putbits(PBIT, 0);  putbits(PBIT, root);
  164.     }
  165.     pos = 0;
  166.     for (i = 0; i < size; i++) {
  167.         if (i % CHAR_BIT == 0) flags = buf[pos++];  else flags <<= 1;
  168.         if (flags & ((unsigned) 1 << (CHAR_BIT - 1))) {
  169.             encode_c((int) (buf[pos++] + ((unsigned) 1 << CHAR_BIT)));
  170.             k = buf[pos++] << CHAR_BIT;  k += buf[pos++];
  171.             encode_p(k);
  172.         } else encode_c((int) buf[pos++]);
  173.         if (unpackable) return;
  174.     }
  175.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  176.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  177. }
  178.  
  179. static uint output_pos, output_mask;
  180.  
  181. void output(c, p)
  182. uint c;
  183. uint p;
  184. {
  185.     static uint cpos;
  186.  
  187.     if ((output_mask >>= 1) == 0) {
  188.         output_mask = (unsigned) 1 << (CHAR_BIT - 1);
  189.         if (output_pos >= bufsiz - 3 * CHAR_BIT) {
  190.             send_block();
  191.             if (unpackable) return;
  192.             output_pos = 0;
  193.         }
  194.         cpos = output_pos++;  buf[cpos] = 0;
  195.     }
  196.     buf[output_pos++] = (uchar) c;  c_freq[c]++;
  197.     if (c >= ((unsigned) 1 << CHAR_BIT)) {
  198.         buf[cpos] |= output_mask;
  199.         buf[output_pos++] = (uchar)(p >> CHAR_BIT);
  200.         buf[output_pos++] = (uchar) p;
  201.         c = 0;  while (p) {  p >>= 1;  c++;  }
  202.         p_freq[c]++;
  203.     }
  204. }
  205.  
  206. void huf_encode_start()
  207. {
  208.     int i;
  209.  
  210.     if (bufsiz == 0) {
  211.         bufsiz = 16 * (unsigned) 1024;
  212.         while ((buf = (uchar *) malloc(bufsiz)) == NULL) {
  213.             bufsiz = (bufsiz / (unsigned) 10) * (unsigned) 9;
  214.             if (bufsiz < 4 * (unsigned) 1024) 
  215.                 prterror('f', no_memory);
  216.         }
  217.     }
  218.     buf[0] = 0;
  219.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  220.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  221.     output_pos = output_mask = 0;
  222.     init_putbits();
  223. }
  224.  
  225. void huf_encode_end()
  226. {
  227.     if (! unpackable) {
  228.         send_block();
  229.         putbits(CHAR_BIT - 1, 0);  /* flush remaining bits */
  230.         putbits(16, 0);                /* EOF marker */
  231.     }
  232. }
  233.  
  234. /***** decoding *****/
  235.  
  236. static void read_pt_len(nn, nbit, i_special)
  237. int nn;
  238. int nbit;
  239. int i_special;
  240. {
  241.     int i, c, n;
  242.     uint mask;
  243.  
  244.     n = getbits(nbit);
  245.     if (n == 0) {
  246.         c = getbits(nbit);
  247.         for (i = 0; i < nn; i++) pt_len[i] = 0;
  248.         for (i = 0; i < 256; i++) pt_table[i] = c;
  249.     } else {
  250.         i = 0;
  251.         while (i < n) {
  252.             c = bitbuf >> (BITBUFSIZ - 3);
  253.             if (c == 7) {
  254.                 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
  255.                 while (mask & bitbuf) {  mask >>= 1;  c++;  }
  256.             }
  257.             fillbuf((c < 7) ? 3 : c - 3);
  258.             pt_len[i++] = c;
  259.             if (i == i_special) {
  260.                 c = getbits(2);
  261.                 while (--c >= 0) pt_len[i++] = 0;
  262.             }
  263.         }
  264.         while (i < nn) pt_len[i++] = 0;
  265.         make_table(nn, pt_len, 8, pt_table);
  266.     }
  267. }
  268.  
  269. static void read_c_len()
  270. {
  271.     int i, c, n;
  272.     uint mask;
  273.  
  274.     n = getbits(CBIT);
  275.     if (n == 0) {
  276.         c = getbits(CBIT);
  277.         for (i = 0; i < NC; i++) c_len[i] = 0;
  278.         for (i = 0; i < 4096; i++) c_table[i] = c;
  279.     } else {
  280.         i = 0;
  281.         while (i < n) {
  282.             c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  283.             if (c >= NT) {
  284.                 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  285.                 do {
  286.                     if (bitbuf & mask) c = right[c];
  287.                     else               c = left [c];
  288.                     mask >>= 1;
  289.                 } while (c >= NT);
  290.             }
  291.             fillbuf((int) pt_len[c]);
  292.             if (c <= 2) {
  293.                 if      (c == 0) c = 1;
  294.                 else if (c == 1) c = getbits(4) + 3;
  295.                 else             c = getbits(CBIT) + 20;
  296.                 while (--c >= 0) c_len[i++] = 0;
  297.             } else c_len[i++] = c - 2;
  298.         }
  299.         while (i < NC) c_len[i++] = 0;
  300.         make_table(NC, c_len, 12, c_table);
  301.     }
  302. }
  303.  
  304. uint decode_c()
  305. {
  306.     uint j, mask;
  307.  
  308.     if (blocksize == 0) {
  309.         blocksize = getbits(16);
  310.         if (blocksize == 0) {
  311. #if 0
  312.             (void) fprintf(stderr, "block size = 0, decoded\n");  /* debug */
  313. #endif
  314.             decoded = 1;
  315.             return 0;
  316.         }
  317.         read_pt_len(NT, TBIT, 3);
  318.         read_c_len();
  319.         read_pt_len(NP, PBIT, -1);
  320.     }
  321.     blocksize--;
  322.     j = c_table[bitbuf >> (BITBUFSIZ - 12)];
  323.     if (j >= NC) {
  324.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
  325.         do {
  326.             if (bitbuf & mask) j = right[j];
  327.             else               j = left [j];
  328.             mask >>= 1;
  329.         } while (j >= NC);
  330.     }
  331.     fillbuf((int) c_len[j]);
  332.     return j;
  333. }
  334.  
  335. uint decode_p()
  336. {
  337.     uint j, mask;
  338.  
  339.     j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  340.     if (j >= NP) {
  341.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  342.         do {
  343.             if (bitbuf & mask) j = right[j];
  344.             else               j = left [j];
  345.             mask >>= 1;
  346.         } while (j >= NP);
  347.     }
  348.     fillbuf((int) pt_len[j]);
  349.     if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
  350.     return j;
  351. }
  352.  
  353. void huf_decode_start()
  354. {
  355.     init_getbits();  blocksize = 0;
  356. }
  357.